﻿#include<iostream>
#include<vector>

using namespace std;

// 第 13 #####################################
//删除并获得点数
//给你一个整数数组 nums ，你可以对它进行一些操作。
//每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
//之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
//开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
//示例 1：输入：nums = [3, 4, 2]    输出：6
//解释：删除 4 获得 4 个点数，因此 3 也被删除。
//之后，删除 2 获得 2 个点数。总共获得 6 个点数。
//
//  初步分析：总是想找到一个方法，能够使的每一个操作总与上一个操作相关
//      第一步：将nums排成有序的
//      第二步：由于以下原因，将对问题进行变形：
//              1. 只要选择删除某个数，该数总是能全部删除
//              2. 只要选择删除某个数，该数的加1的结果和减1的结果都不能选
//          变形步骤：
//          step1: 对所给序列进行计数排序
//          step2: 将排序后的数组元素的值和其数组下标相乘，
//                 形成可用动态规划算法求解的新问题对应的数组σ
//      第三步：新问题：在σ中找几个元素求和，和最大
//                要求：找到的元素不能相邻
// 
//  1. 状态表示：以某个位置为结尾选择dp[i]
//       dp[i]: 从第一个元素到第i个位置最大和
// 
//  2. 状态转移方程：此时的dp[i]需要借助两个辅助函数，f[i], g[i]
//	   其中f[i]表示：到i位置时，选择nums[i]，此时的最大和
//		   g[i]表示：到i位置时，不选nums[i]，此时的最大和
//	   f[i] = g[i - 1] + nums[i]    g[i] = max{f[i - 1], g[i - 1]}
// 
//  3. 初始化及迭代方向
//     f[0] = nums[0]   g[0] = 0;
//
class Solution1 {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int N = 10001;
        int auxiarr[N] = { 0 };
        //  要完成以下两步，也可以用下面的代码
        //  step1: 对所给序列进行计数排序
        //  step2: 将排序后的数组元素的值和其数组下标相乘，
        //         形成可用动态规划算法求解的新问题对应的数组σ
        for (auto num : nums) auxiarr[num] += num;

        vector<int> f(N);
        auto g = f;
        for (int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + auxiarr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[N - 1], g[N - 1]);
    }
};

// 第 14 #####################################
// 粉刷房子
//假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，
//你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
//当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
//每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
//例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；
//costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
//请计算出粉刷完所有房子最少的花费成本。
//示例 1：输入 : costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]    输出 : 10
//解释 : 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
//最少花费 : 2 + 5 + 3 = 10。
//
// 初步分析：刷完所有房子的后的最小总花费，可以先确定最后一个房子刷的颜色
//       若已知最后一个房子刷红色，
//           总花费等于
//           min(刷完N-1个房子后的最小总花费(且倒数第二个房子刷蓝色)，
//              刷完N-1个房子后的最小总花费(且倒数第二个房子刷绿色))
//       若已知最后一个房子刷绿色，或者蓝色同理
// 
//    1. 状态表示：以某个位置为结尾选择dp[i][j],
//       dp[i][j]: 从第一个房子刷到第i个房子(且第i个房子刷j色)的最小总花费
//       j = 0, 1, 2 其中0，1，2分别代表红，蓝，绿; i从1开始取值
//   
//    2. 状态转移方程
//       dp[i][0] = min{ dp[i - 1][1], dp[i - 1][2] } + costs[i - 1][0]
//       dp[i][1] = min{ dp[i - 1][0], dp[i - 1][2] } + costs[i - 1][1]
//       dp[i][2] = min{ dp[i - 1][0], dp[i - 1][1] } + costs[i - 1][2]
// 
//    3. 初始化及迭代方向
//       dp[1][0] = costs[0][0] 为和2. 匹配，即想让下式成立
//       dp[1][0] = min{ dp[0][1], dp[0][2] } + cost[0][0]
//       可以让   dp[0][0] = dp[0][1] = dp[0][2] = 0
//
class Solution2 {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));
        for (size_t i = 1; i <= n; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        return min(min(dp[n][0], dp[n][1]), dp[n][2]);
    }
};

// 第 15 #####################################
// 买卖股票的最佳时机含冷冻期 (medium)
//给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
//设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票） :
//卖出股票后，你无法在第二天买入股票(即冷冻期为 1 天)。
//注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//示例 1:  输入: prices = [1, 2, 3, 0, 2]   输出 : 3 
//解释 : 对应的交易状态为 : [买入, 卖出, 冷冻期, 买入, 卖出]
//
//    初步分析：建立状态机，分析状态和动作
//        第i - 1天收盘时，参与者的状态有三种：
//            1. 手上持有股票(简称买入状态)
//            2. 手上未持有股票，且有买入股票的权力(简称可交易状态)
//            3. 手上未持有股票，且没有买入股票的权力(简称冷冻期)
//        第i天开盘时，可以进行的动作有三种：
//            1. 花费prices[i]，在第i天购买一只股票
//            2. 卖出一只股票，收获prices[i]
//            3. 不做任何操作
// 
// 状态机：画出所有状态，并且画出所有状态可以进行的动作与其自身状态和其它状态的关系
//     买入状态 - 不做操作 -> 买入状态
//     买入状态 - 卖出操作 -> 冷冻期
// 
//     可交易状态 - 买入操作 -> 买入状态
//     可交易状态 - 不做操作 -> 可交易状态
// 
//     冷冻期 - 不做操作 -> 可交易状态
// 
//  1. 状态表示：以第i天结束时的最大利润为结尾选择dp[i][j],
//     dp[i][0]， dp[i][1]， dp[i][2]分别代表
//     第i天结束了，且参与者处于买入状态的最大利润
//     第i天结束了，且参与者处于可交易状态的最大利润
//     第i天结束了，且参与者处于冷冻期的最大利润
// 
//  2. 状态转移方程：
//         dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0])
//         dp[i][1] = max(dp[i - 1][1], dp[i - 1][2])
//         dp[i][2] = dp[i - 1][0] + prices[i]
// 
//  3. 初始化及迭代方向
//     只能在第0天的时候购买股票才能处于买入状态，此时dp[0][0] = -prices[0] 
//     dp[0][1] = 0        dp[0][2] = 0
//
class Solution3 {
public:
    int maxProfit(vector<int>& prices) {
        int numofday = prices.size();
        vector<vector<int>> dp(numofday, vector<int>(3));
        dp[0][0] = (-1) * prices[0];
        for (size_t i = 1; i < numofday; i++)
        {
            dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        //最后一天开盘的时候如果执行了买入操作，则收盘的时候一定不是最大利润
        //也就是最后一天收盘的时候如果处于买入状态(因为买入操作只能到买入状态)，则收盘的时候一定不是最大利润
        return max(max(dp[numofday - 1][0], dp[numofday - 1][1]), dp[numofday - 1][2]);
    }
};

int main()
{
    return 0;
}